This invention relates to the use of check codes in data transmission systems for detecting errors in the transmission of data, and particularly to a method and system for employing systematic check codes for detecting a predetermined number of unidirectional errors in the transmission of data.
In a digital computer or communications system it is desirable, and sometimes vital, that data be reliable when stored, retrieved, communicated, or otherwise manipulated. The complexity of modern computer and communication systems makes it impractical to depend solely upon reliable components and devices for reliable system operation. Some redundancy is needed for detection of errors, which will invariably occur as information is being stored, retrieved, transferred, or manipulated.
The types of error patterns which occur in memory, logic, and arithmetic units are many and varied. However, they can broadly be classified as "symmetric," "asymmetric," and "unidirectional" errors. Error patterns in digital systems are said to be symmetric when both 1 to 0 and 0 to 1 errors can occur simultaneously in a data word. When the errors produced in a data word by a digital system are of only one type, say 1 to 0, the error pattern is called asymmetric. In the latter case the other type of error, that is, 0 to 1, will never occur in any data word. When the errors produced in a data word by a digital system may be either 0 to 1 or 1 to 0, but not both simultaneously, the error pattern is called unidirectional. In the latter case, while the data word has only 0 to 1 errors or only 1 to 0 errors, the type of errors are not a priori determinable. In addition, errors may be considered as "bursts," that is, errors which lie within a set of adjacent bits of a data word.
All or part of a digital data system may be characterized as having a data source for producing a data word, a data sink for accepting the data word, and a data transmission channel for transmitting a data word from the data source to the data sink. One method for detecting errors that occur in the transmission of a data word from the data source to the data sink is to incorporate in the data word prior to transmission a check code, comprising one or more check bits, and employing those check bits at the data sink to detect the occurrence of a transmission error. An example of such a system is disclosed in Hamming et al. U.S. Pat. No. 2,552,629. Such an apparatus is capable of detecting up to three symmetric errors or correcting one symmetric error. Moreover, an extensive theory of symmetric error control coding has been developed, as discussed in E. R. Berlekamp, "Algebraic Coding Theory" (McGraw-Hill, 1968); S. Lin, "An Introduction to Error-Correcting Codes" (Prentice-Hall, 1970); W. W. Peterson and E. J. Weldon, "Error Correcting Codes" (MIT Press, 1972); and N. J. A. Sloane and F. J. MacWilliams, "The Theory of Error Correcting Codes" (North-Holland, 1978).
The error patterns of some recently developed very large scale integrated circuits are of the unidirection type. While symmetric error code detection systems could be utilized to detect errors occuring in such circuits, each check bit included in a data word will necessarily decrease the rate at which information may be transmitted over a data channel. Moreover, in many digital data systems the probability of more than a predetermined number of errors occuring is so low that it is not cost effective to attempt to detect conditions where more than that number of errors occurs. It would therefore be desirable to minimize the number of check bits required to detect errors by detecting only up to a predetermined number of unidirectional errors. It is also desirable, in employing check codes, to use systematic codes, that is, codes in which the information bits are separately identified from the check bits, so that encoding, decoding, and data manipulation, can be performed in parallel bit logic. The unidirectional error codes previously known are non-systematic constant weight codes and systematic Berger-Freiman codes, as described in J. M. Berger, "A Note on Error Detecting Codes for Asymmetric Channels," Information and Control, Vol. 4, pp. 68-73 (March, 1961), and C. V. Freiman, "Optimal Error Detecting Codes for Completely Asymmetric Binary Channel," Information and Control, Vol. 5, pp. 64-71 (March, 1962), both of which detect all unidirectional errors in a data word. However, the aforementioned codes are not optimal when only up to a predetermined number of errors greater than one need be detected.